import entity.TreeNode;

public class TrimBST {
    /*
    * 669. 修剪二叉搜索树
    * 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。
    * 通过修剪二叉搜索树，使得所有节点的值在[low, high]中。
    * 修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。
    * 可以证明，存在 唯一的答案 。
    * 所以结果应当返回修剪好的二叉搜索树的新的根节点。
    * 注意，根节点可能会根据给定的边界发生改变。
    *
    * 树中节点数在范围 [1, 10^4] 内
    * 0 <= Node.val <= 10^4
    * 树中每个节点的值都是 唯一 的
    * 题目数据保证输入是一棵有效的二叉搜索树
    * 0 <= low <= high <= 10^4
    * */
    public static void main(String[] args){

    }

    // 我的想法：递归，利用BST的特性，
    // 对于下限，一旦找到小于最小值的节点，其以及其左子树全都要删除，保留右子树，继续比较，直到不需删除
    // 对于上限，一旦找到大于最小值的节点，其以及其右子树全都要删除，保留左子树，继续比较，直到不需删除
    // 过啦！
    public TreeNode mySolution(TreeNode root, int low, int high){
        if(root == null)
            return null;
        if(root.val >= low && root.val <= high){
            root.left = mySolution(root.left, low, high);
            root.right = mySolution(root.right, low, high);
            return root;
        }
        else {
            if(root.val < low){
                root.right = mySolution(root.right, low, high);
                return root.right;
            }
            else {
                root.left = mySolution(root.left, low, high);
                return root.left;
            }
        }
    }
}
